9.54 The clique problem can be stated as follows: Given an undirected graph G = (V, E) and an integer K, does G contain a complete subgraph of at least K vertices? The vertex cover problem can be stated as follows: Given an undirected graph G = (V, E) and an integer K, does G contain a subset V ⊂ V such that |V | ≤ K and every edge in G has a vertex in V ? Show that the clique problem is polynomially reducible to vertex cover. - | |
| View Solution | |
| << Back | Next >> |